#include <ctime>
#include "BalanceTree.h"

using namespace std;

template <typename T>
// normal sort function.
// i/o param:_data
// input the elments into BST and
// medium order traversal.
// print the sorted vertor.
void AVL_BST_sort(vector<T> &_data) {
    AVLTree<T> tree;
    for (int i=0;i<_data.size();++i) {
        tree.insert(_data[i]);
    }
    _data.clear();
    while (!tree.isEmpty()) {
        _data.push_back(tree.findMin());
        tree.remove(tree.findMin());
    }
};

template <typename T>
// normal sort function.
// i/o param:_data
// input the elments into BST and
// medium order traversal.
// print the sorted vertor.
void Splay_BST_sort(vector<T> &_data) {
    SplayTree<T> tree;
    for (int i=0;i<_data.size();++i) {
        tree.insert(_data[i]);
    }
    _data.clear();
    while (!tree.isEmpty()) {
        _data.push_back(tree.findMin());
        tree.remove(tree.findMin());
    }
};


int main() {
    vector<int> vec1,vec2;
    int n,number;
    cout<<"input n : （推荐输入5）";
    while (cin>>n && n) {
        cout<<"推荐输入1、2、3、4、5的任意排列组合"<<endl;
        for (int i=0;i<n;++i) {
            cin>>number;
            vec1.push_back(number);
            vec2.push_back(number);
        }
        clock_t start_time1=clock();
        AVL_BST_sort(vec1);
        clock_t end_time1=clock();
        for (int i=0;i<n;++i) {
            cout<<vec1[i]<<" ";
        }
        cout<<endl<<"time of avl_sort : "<<double(end_time1-start_time1)/CLOCKS_PER_SEC<<"s"<<endl;
        clock_t start_time2=clock();
        Splay_BST_sort(vec2);
        clock_t end_time2=clock();
        for (int i=0;i<n;++i) {
            cout<<vec2[i]<<" ";
        }
        cout<<endl<<"time of splay_sort : "<<double(end_time2-start_time2)/CLOCKS_PER_SEC<<"s"<<endl;

    }
}

